2-2

Spectral Bounds

Nicholas Wheeler
2 September 2011

While browsing in M. Aigner & G. M. Ziegler's Proofs from THE BOOK (1998) this morning—it has for several weeks provided my primary bathroom reading material—I came upon a theorem first obtained by Laguerre, and presented here as a consequence of the inequalities

harmonic mean ⩽ geometric mean ⩽ arithmetic mean

THEOREM: Suppose all roots of the polynomial

(x^n)+(Subscript[a, n-1])(x^(n-1))+(Subscript[a, n-2])(x^(n-2)) ... +(Subscript[a, 0])

are real. Then the roots are contained in the interval with endpoints

-((Subscript[a, n-1])/n)± ((n-1)/n)(Sqrt[((Subscript[a, n-1])^2)-((2n)/(n-1))(Subscript[a, n-2])])

I am curious to know whether this pretty result permits one to place useful bounds on the spectra of finite-dimensional hermitian (or real symmetric) matrices.

The eigenvalues of a real or complex hermitian matrix are known to be real. The characteristic polynomial of such a matrix 𝔸 can be developed (I quote now from my "Trace of Inverted Matrix" [pdf file: December 1996])

(∑_(k=0)^n)(1/(k!))(Subscript[Q, k])(((-x))^(n-k))=(Subscript[Q, 0])(((-x))^n)+(Subscript[Q, 1])(((-x))^(n-1))+(1/2)(Subscript[Q, 2])(((-x))^(n-2))+⋯

where

(Subscript[Q, 0])=1
(Subscript[Q, 1])=(Subscript[T, 1])
(Subscript[Q, 2])=((Subscript[T, 1])^2)-(Subscript[T, 2])
     ⋮

with (Subscript[T, k])=Tr[(𝔸^k)]. To render the polynomial described above into the monic form presumed by the theorem, we divide by (((-))^n)(Subscript[Q, 0])=(((-))^n), to obtain

(x^n)-(Subscript[T, 1])(x^(n-1))+((((Subscript[T, 1])^2)-(Subscript[T, 2]))/2)(x^(n-2))+⋯ ≡(x^n)+(Subscript[a, n-1]) (x^(n-1))+ (Subscript[a, n-2]) (x^(n-2))+ ⋯

whence

(Subscript[a, n-1])=-(Subscript[T, 1])
(Subscript[a, n-2])=((((Subscript[T, 1])^2)-(Subscript[T, 2]))/2)

In this notation, the spectral bounds asserted by Laguerre's theorem become, after simplifications,

((Subscript[T, 1])/n)± ((n-1)/n)(Sqrt[((n(Subscript[T, 2])-((Subscript[T, 1])^2))/(n-1))])

where n is the dimension of the square matrix 𝔸.

EXPERIMENTAL TESTS: Look first to random matrices that, by the Perron-Frobenius theorem, are expected to have a solitary large eigenvalue. Many runs indicate that the upper Laguerre bound does typically provide a rough estimate of the maximal eigenvalue, but that the lower Laguerre bound is typically very wide of the mark.

𝔸=((𝕄+Transpose[𝕄])/2)/.𝕄->RandomReal[{},{10,10}];

((Tr[𝔸])/10)+ ((10-1)/10)(Sqrt[((10Tr[𝔸.𝔸]-((Tr[𝔸])^2))/(10-1))])
Max[Eigenvalues[𝔸]]
Min[Eigenvalues[𝔸]]
((Tr[𝔸])/10)- ((10-1)/10)(Sqrt[((10Tr[𝔸.𝔸]-((Tr[𝔸])^2))/(10-1))])

If we give up positivity of the matrix elements we lose the isolated large eigenvalue, but the Laguerre bounds still behave as though it were to be expected:

𝔹=((𝕄+Transpose[𝕄])/2)/.𝕄->RandomReal[{-1,1},{10,10}];

((Tr[𝔹])/10)+ ((10-1)/10)(Sqrt[((10Tr[𝔹.𝔹]-((Tr[𝔹])^2))/(10-1))])
Max[Eigenvalues[𝔹]]
Min[Eigenvalues[𝔹]]
((Tr[𝔹])/10)- ((10-1)/10)(Sqrt[((10Tr[𝔹.𝔹]-((Tr[𝔹])^2))/(10-1))])

But in all cases the Laguerre bounds do in fact bracket the spectrum; they just don't provide very accurate estimates of its extrema.

Note added on 25 September

Instead of by-hand repetition of the preceding command we can automatically do so many time, and plot the results…which will serve to expose the regularity of the results. To illustrate the procedure I look again to the case of symmetric 10 × 10 matrices, with elements selected at random from the unit interval:

upper[x_]:=((Tr[x])/10)+ ((10-1)/10)(Sqrt[((10Tr[x.x]-((Tr[x])^2))/(10-1))])
lower[x_]:=((Tr[x])/10)- ((10-1)/10)(Sqrt[((10Tr[x.x]-((Tr[x])^2))/(10-1))])

SpectralBoundsData=Flatten[Table[{upper[𝔸],lower[𝔸]}/.𝔸->((𝕄+Transpose[𝕄])/2)/.𝕄->RandomReal[{},{10,10}],{k,1,1000}]];

DisplayBounds=ListPlot[SpectralBoundsData,PlotRange->{-6,7}]

One could look to the means and variances of the upper/lower bounds, and to how they depend upon  dimension and properties of the statistic that generates the matrix elements. 

Simultaneous display of the following figures

DisplayEigenvalues=ListPlot[Flatten[Table[Eigenvalues[𝔸]/.𝔸->((𝕄+Transpose[𝕄])/2)/.𝕄->RandomReal[{},{10,10}],{k,1,200}]], PlotStyle->Red, PlotRange->{-6,7}]

Show[{DisplayBounds, DisplayEigenvalues}]

It is interesting that the upper bound does capture—and pretty well approximate—the "exceptionally large leading eigenvalues" dictated by the Perron-Frobenius Theorem.